package com.datastructure.test.kbtree;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class KBtree {
    public int length = 0;
    public int index = 0;
    public static void main(String[] args) {
        KBtree kBtree = new KBtree();
        TreeNode treeNode = new TreeNode(5);
        treeNode.left=new TreeNode(3);
        treeNode.right=new TreeNode(7);
        treeNode.left.left=new TreeNode(2);
        treeNode.left.right=new TreeNode(4);
        treeNode.right.left=new TreeNode(6);
        treeNode.right.right=new TreeNode(8);
        int i = kBtree.KthNode1(treeNode, 3);
        System.out.println(i);
    }

    int count = 0;    //标记遍历的节点数
    int result = -1;
    public int KthNode1 (TreeNode proot, int k) {
        if(proot == null || k <= 0)    return -1;
        KthNode1(proot.left,k);
        ++count;
        if(count == k)    return result = proot.val;
        KthNode1(proot.right,k);
        return result;
    }

    public int KthNode (TreeNode proot, int k) {
        // write code here
        if(proot==null){
            return -1;
        }
        getLength(proot);
        int[] data = new int[length];
        insertValue(proot,data);
        quickSort(data,0,data.length-1);
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < data.length; i++) {
            set.add(data[i]);
        }
        Iterator<Integer> iterator = set.iterator();
        int index=0;
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            index++;
            if(index==k){
                return next;
            }
        }
        return -1;
    }

    public void quickSort(int[] data, int start, int end){
        if(start<end){
            int divideIndex = getDivideIndex(data, start, end);
            quickSort(data,start,divideIndex-1);
            quickSort(data,divideIndex+1,end);
        }
    }

    private int getDivideIndex(int[] data, int start, int end) {
        int initIndex=start;
        int initValue=data[initIndex];
        while (start<end){
            while (start<end&&data[end]>=initValue){
                end--;
            }
            while (start<end&&data[start]<=initValue){
                start++;
            }
            if(start<end){
                swap(data,start,end);
            }
        }
        if(start==end){
            data[initIndex]=data[start];
            data[start]=initValue;
        }
        return start;
    }

    public void swap(int[] data,int start,int end){
        int temp = data[start];
        data[start]=data[end];
        data[end]=temp;
    }

    public void insertValue(TreeNode root,int [] data){
        if(root!=null){
            data[index]= root.val;
            index++;
        }else {
            return;
        }
        if(root.left!=null){
            insertValue(root.left,data);
        }
        if(root.right!=null){
            insertValue(root.right,data);
        }
    }

    public void getLength(TreeNode root){
        if(root!=null){
            length++;
        }else {
            return;
        }
        if(root.left!=null){
            getLength(root.left);
        }
        if(root.right!=null){
            getLength(root.right);
        }
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
 }
